package com.demo.java.OD301_350.OD330;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【数据最节约的备份方法(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146119812
 */
public class OdMain {
    public static void main(String[] args) {
        // 创建Scanner对象来读取输入
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        scanner.close();

        // 将输入的字符串按逗号分割并转换为整数数组
        String[] numStr = input.split(",");
        int[] nums = Arrays.stream(numStr).mapToInt(Integer::parseInt).toArray();

        // 对文件大小进行排序，贪心算法需要
        Arrays.sort(nums);

        // 调用计算最少硬盘数量的函数
        int count = countMinimumDisks(nums);

        // 输出最终所需硬盘数量
        System.out.print(count);
    }

    // 计算最少需要的硬盘数量
    private static int countMinimumDisks(int[] nums) {
        // 使用ArrayList模拟硬盘的分配
        ArrayList<Integer> availableDisks = new ArrayList<>(nums.length);

        // 将每个文件大小放入一个硬盘列表中
        for (int num : nums) {
            availableDisks.add(num);
        }

        int count = 0;  // 用来记录硬盘的数量
        // 当还有文件未分配时
        while (!availableDisks.isEmpty()) {
            int currentDiskSpace = 0;  // 当前硬盘使用的空间

            // 从文件列表的末尾（即文件大小较大的部分）开始尝试填充硬盘
            for (int i = availableDisks.size() - 1; i >= 0; i--) {
                int diskSize = availableDisks.get(i);
                // 如果当前硬盘空间加上这个文件大小不超过500MB
                if (diskSize + currentDiskSpace <= 500) {
                    currentDiskSpace += diskSize;  // 将文件加入当前硬盘
                    availableDisks.remove(i);  // 移除已分配的文件
                }
            }
            count++;  // 每次填充完一个硬盘，硬盘数量加1
        }

        return count;  // 返回最终硬盘的数量
    }
}